package graph;


import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.LinkedList;

import java.util.Set;


public class Graph {

    private Set<Vertex> vertices = new HashSet<Vertex>();
    private Set<Edge>  edge = new HashSet<Edge>();
    private HashMap<String, Vertex> my_map = new HashMap<String, Vertex>();
    private int numberOfPowerSet;
    
    
    public Graph(Set<Vertex> verts, Set<Edge> edges) {
        Set<Vertex> clonedListVertex = new LinkedHashSet<Vertex>();
        for (Vertex ve : verts) {
            clonedListVertex.add(ve);
        }
        vertices = clonedListVertex;
        Set<Edge> clonedListEdges = new LinkedHashSet<Edge>();
        for (Edge ed : edges) {
            clonedListEdges.add(new Edge(ed.getVertex1(), ed.getVertex2(),
                    ed.getCost()));
        }
        edge = clonedListEdges;
        for (Vertex s: vertices) {
            s.setEdge(edge);
            //now creating my HashMap
            my_map.put(s.toString(), s);
        }       
    }

    public String toString() { 
        final StringBuilder sb = new StringBuilder();
        sb.append("Graph\n");
        sb.append("Vertices: \n");
        for (Vertex s : vertices){
            sb.append(s.toString() + " ");
        }

        sb.append("\nEdges:\n");
        for (Edge e : edge){
            sb.append(e.toString() + "\n");
        }

        return sb.toString();
    }

    public Set<Edge> getEdges() { 
        return edge;
    }


    public void addEdge(String v1, String v2, double cost) {
        this.edge.add(new Edge(my_map.get(v1), my_map.get(v2), cost));
        my_map.get(v1).setEdge(edge);
        my_map.get(v2).setEdge(edge);
    }

    public void addEdge(Edge e) { 
        edge.add(e);
    }

    public void removeEdge(Edge e) { 
        edge.remove(e);
    }

    public Set<Vertex> getVertices() { 
        return vertices;
    }

    public Vertex getVertex(String vName) {
        //check if vertex is in the same graph, exception otherwise.

        return my_map.get(vName);
    }

    public boolean isConnected() {
		boolean result = false;
		LinkedList<Vertex> vertArray = new LinkedList<Vertex>(this.vertices);
		LinkedList<LinkedList<String>> lists = new LinkedList<LinkedList<String>>();
		int max = 0;
		LinkedList<String> finalList = new LinkedList<String>();
		for(int i = 0; i < vertArray.size(); i++){
			LinkedList<String> toExplore = new LinkedList<String>();
			LinkedList<String> done = new LinkedList<String>();
			toExplore.add(vertArray.get(i).toString());
			done.add(vertArray.get(i).toString());
			while(!toExplore.isEmpty()){
				//Set<Edge> curr = toExplore
				for (Edge e : (this.my_map.get(toExplore.pop().toString())).getEdge()){
					if(!done.contains(e.getVertex2().toString())){
						toExplore.add(e.getVertex2().toString());
						done.add(e.getVertex2().toString());
					}
					else if(!done.contains(e.getVertex1().toString())){
						toExplore.add(e.getVertex1().toString());
						done.add(e.getVertex1().toString());
					}
				}
			}
			lists.add(done);
			//System.out.println("List checked: " + done);
		}
		for (int j = 0; j < lists.size(); j++){
			if (lists.get(j).size() >= max){
				max = lists.get(j).size();
				finalList = lists.get(j);
			}
		}
		if (finalList.size() == this.vertices.size()){
			result = true;
		}
		else result = false;
		return result;
	}

    private Set<Vertex> cloneVertexSetbyName(Set<Vertex> v){
		Set<Vertex> clonedListVertex = new LinkedHashSet<Vertex>();
		String name = "";
		Vertex temp;
		for (Vertex ve : v) {
			name = ve.toString();
			temp = new Vertex(name);
			clonedListVertex.add(temp);
		}
		return clonedListVertex;
	}
    
	public boolean isRedConnected() {
		return isRedConnected(edge);
	}

    
    public boolean isRedConnected(Set<Edge> ed) {
		Graph tempGraph = new Graph(cloneVertexSetbyName(vertices), cloneEdgeSet(ed));
		boolean answer = false;
		//only processing the connected graphs
		if (tempGraph.isConnected()){
			Iterator<Edge> iter = tempGraph.edge.iterator();
			Edge curr;
			Set<Edge> tempEdges;
			while(iter.hasNext()){
				curr = iter.next();
				System.out.println("curr = " + curr);
				System.out.println("before removing " + tempGraph.getEdges());
				tempGraph.removeEdge(curr);
				Set<Edge> afterRemoveSet = tempGraph.getEdges();
				//tempGraph.setAdjacent(afterRemoveSet);
				System.out.println("the temporary set after removing: "+ tempGraph.getEdges());
				if (tempGraph.isConnected()){
					System.out.println("is connected: "+ tempGraph.isConnected());
					// this means is REDconnected
					tempGraph.addEdge(curr);
					afterRemoveSet = tempGraph.getEdges();
					//tempGraph.setAdjacent(afterRemoveSet);
					System.out.println("after adding " + tempGraph.getEdges());
					answer = true;
					break;
				} else {
					tempGraph.addEdge(curr);
					afterRemoveSet = tempGraph.getEdges();
					//tempGraph.setAdjacent(afterRemoveSet);
					
				}
			} // end of while
		} // end of if
		return answer;
	}


	private Set<Edge> minRedGraph() {
		double minCost = Double.longBitsToDouble(0x7fefffffffffffffL);

		Set<Edge> minSetCost = cloneEdgeSet(edge);
		Set<Set<Edge>> edgePowerSet = getPowerSet(edge);
		Set<Set<Edge>> toCheckCost = new HashSet<Set<Edge>>();
		Iterator<Set<Edge>> iter = edgePowerSet.iterator();
		Set<Edge> curr;

		while(iter.hasNext()){
			curr = iter.next();
			if (isRedConnected(curr)){
				toCheckCost.add(curr);
			}
		}

		System.out.println("PowerSets REDconnected:");
		System.out.println(toCheckCost);

		for (Set<Edge> ed: toCheckCost) {
			if (totalCostEdges(ed) < minCost) {
				minCost = totalCostEdges(ed);
				System.out.println("Edges: " + ed);
				System.out.println("and its cost = " + minCost);
				minSetCost = cloneEdgeSet(ed);
			}
		}
		System.out.println(minSetCost);
		return minSetCost;	
	}
    


    private Set<Edge> cloneEdgeSet(Set<Edge> e){
        Set<Edge> clonedListEdges = new LinkedHashSet<Edge>();
        for (Edge ed : e) {
            clonedListEdges.add(new Edge(ed.getVertex1(), ed.getVertex2(), 
                    ed.getCost()));
        }
        return clonedListEdges;
    }

    private Set<Vertex> cloneVertexSet(Set<Vertex> v){
        Set<Vertex> clonedListVertex = new LinkedHashSet<Vertex>();
        for (Vertex ve : v) {
            clonedListVertex.add(ve);
        }
        return clonedListVertex;
    }
    
    private double totalCostEdges(Set<Edge> ed) { 
		Iterator<Edge> iter = ed.iterator();
		Edge e;
		double sum = 0;
		while(iter.hasNext()){
			e = iter.next();
			sum = sum + e.getCost();
		}
		return sum;   
	}

    public Set<Set<Edge>> getPowerSet(Set<Edge> e) {
        Set<Set<Edge>> powerSet = new HashSet<>(), runSet = new HashSet<>(), 
                thisSet = new HashSet<>();
                while(powerSet.size() < (Math.pow(2, e.size())-1)) {              
                    if(powerSet.isEmpty()) {
                        for(Edge o : e) {
                            Set<Edge> s = new HashSet<>();//TreeSet<>();
                            s.add(o);
                            runSet.add(s);
                            powerSet.add(s);
                        }
                        continue;
                    }
                    for(Edge o : e) {
                        for(Set<Edge> s : runSet) {
                            Set<Edge> s2 = new HashSet<>();//TreeSet<>();
                            s2.addAll(s);
                            s2.add(o);
                            powerSet.add(s2);
                            thisSet.add(s2);
                        }
                    }
                    runSet.clear();
                    runSet.addAll(thisSet);
                    thisSet.clear();
                }
                powerSet.add(new HashSet<Edge>());
                numberOfPowerSet = powerSet.size();
                System.out.println(numberOfPowerSet); // for testing purposes, remove later
                return powerSet;
    }
    
    /**
     * Get total costs.
     * @return a double for cost.
     */
    // redundantly connected
    public double totalEdgeCost() { 

        double costs = 0;
        //for ech
        for (Edge e : edge){
            costs = costs + e.getCost();
        }
        return costs;
    }


}
